In the design and implementation of in-memory databases, data may be loaded into memory using pages, such that each page can be handled as a unit. Given limited space in memory, when data in a page is no longer needed, the page may be committed to persistent or longer-term storage and evicted from memory. With implementations of pages or data entries each having a fixed size, any page or allocated space for data entries may be freed or otherwise evicted, and any other page may be loaded in place of the previous page. However, when using entries of variable sizes, once a an entry is evicted or otherwise de-allocated, the next entry to be added into memory may not fit into the same space of the evicted entry, thereby necessitating use of a larger set of contiguous free space in memory.
The larger set of contiguous space may lack the same spatial and temporal locality as the freed space from the evicted page or entry, potentially making the database slower and more difficult to manage, with more overhead in accessing and processing the data entries. Also, the handling of free space becomes less efficient, further depleting sets of contiguous space while other small gaps remain scattered throughout. Conventional techniques for managing or working around these gaps also add significant overhead, while not employing any such techniques will still inevitably lead to other performance problems, from suboptimal speed to excess memory usage to failures in accessing or processing data.
in the drawings, like reference numbers generally indicate identical or similar elements. Additionally, generally, the left-most digit(s) of a reference number identifies the drawing in which the reference number first appears.